package data_structure.mooc;

import data_structure.helper.ArrayGenerator;
import data_structure.helper.SortingHelper;

import java.util.Arrays;

public class LSDSort {

    private LSDSort() {

    }

    /**
     * least significant digit，字符串排序，稳定
     * @param arr String
     * @param w 字符串的长度，要求待排序的字符串等长
     */
    public static void sort(String[]arr,int w){

        //处理异常
        for (String s : arr) {
            if(s.length ()!=w){
                throw new IllegalArgumentException("the length of string must be same");
            }
        }
        //从w-1开始，依次对每一位元素进行计数排序
        int r=256;
        int []cnt=new int[r];
        int []index=new int[r+1];
        String []temp=new String[arr.length];
        for(int i=w-1;i>=0;i--){

            Arrays.fill (cnt,0);
            for (String s : arr) {
                cnt[s.charAt(i)]++;
            }

            for(int j=0;j+1<index.length; j++){
                index[j+1]=index[j]+cnt[j];
            }
            for (String s : arr) {
                temp[index[s.charAt (i)]]=s;
                index[s.charAt(i)]++;
            }
            for(int k = 0; k <arr.length; k++){
                arr[k]=temp[k];
            }
        }
    }

    public static void main(String[] args) {
        int n=100000;
        int w=200;
        String []arr= ArrayGenerator.generateRandomString (n,w);
        String []arr2=Arrays.copyOf(arr, arr.length);

        SortingHelper.testSorting (arr,"quickSort");
        SortingHelper.testSorting(arr,"LSDSort");
    }
}
